/***********************************************************************
 * Copyright © 2013 Beals Software
 * All Rights Reserved
************************************************************************
Author: Donald Beals
Date: August 28, 2013
Description: An object to simplify A* pathfinding.
polygonpathfinding.codeplex.com
****************************** Change Log ******************************
08.28.13 - Created initial file. (dbeals)
***********************************************************************/

function Pathfinder()
{
	this.trimPaths = false;
	this.checkNode = function(column, row)
	{
		return true;
	}
	
	this.createPath = function(node)
	{
		var points = new Array();
		var parent = node;
		
		while(parent != null)
		{
			points.unshift(parent.position);
			parent = parent.parent;
		}
		
		depth = points.length;
		
		if(this.trimPaths)
		{
			// @TODO: This definitely will need to be improve, mainly the splice at the end.
			var indicesToRemove = new Array();
			for(var index = 1; index < points.length - 1; ++index)
			{
				var previousPoint = points[index - 1];
				var currentPoint = points[index];
				var nextPoint = points[index + 1];
				
				if(
					(currentPoint.x == nextPoint.x && currentPoint.y != nextPoint.y && nextPoint.x == previousPoint.x) ||
					(currentPoint.y == nextPoint.y && currentPoint.x != nextPoint.x && nextPoint.y == previousPoint.y))
					indicesToRemove.push(index);
			}
			
			for(var index = indicesToRemove.length - 1; index >= 0; --index)
				output.splice(indicesToRemove[index], 1);
		}
		
		return { 'points': points, 'depth': depth };
	}
	
	this.checkNodeList = function(nodes, point)
	{
		for(var index = 0; index < nodes.length; ++index)
		{
			var node = nodes[index];
			if(node.position.x == point.x && node.position.y == point.y)
				return true;
		}
		return false;
	}
	
	this.processNode = function(currentNode, columnOffset, rowOffset, openNodes, closedNodes)
	{
		var newNode = new PathTreeNode(new Point(currentNode.position.x + columnOffset, currentNode.position.y + rowOffset), currentNode, 0);
		if((this.checkNode == null || this.checkNode(newNode.position.x, newNode.position.y)) &&
			!this.checkNodeList(closedNodes, newNode.position) &&
			!this.checkNodeList(openNodes, newNode.position))
		{
			openNodes.push(newNode);
			return newNode;
		}
		return null;
	}
	
	this.findPath = function(startPosition, endPosition)
	{
		var closedNodes = new Array();
		var openNodes = new Array();
		
		openNodes.push(new PathTreeNode(startPosition, null, 0));
		
		while(true)
		{
			if(openNodes.length == 0)
				return { "points": null, "depth": 0 };
				
			var currentNode = openNodes[0];
			var currentPosition = currentNode.position;
			
			if(jQuery.inArray(currentNode, closedNodes) == -1)
			{
				if(currentPosition.x == endPosition.x && currentPosition.y == endPosition.y)
					return this.createPath(currentNode);
					
				var left = this.processNode(currentNode, -1, 0, openNodes, closedNodes);
				var up = this.processNode(currentNode, 0, -1, openNodes, closedNodes);
				var right = this.processNode(currentNode, 1, 0, openNodes, closedNodes);
				var down = this.processNode(currentNode, 0, 1, openNodes, closedNodes);
				
				if(left != null && up != null)
					this.processNode(currentNode, -1, -1, openNodes, closedNodes);
				if(right != null && up != null)
					this.processNode(currentNode, 1, -1, openNodes, closedNodes);
				if(right != null && down != null)
					this.processNode(currentNode, 1, 1, openNodes, closedNodes);
				if(left != null && down != null)
					this.processNode(currentNode, -1, 1, openNodes, closedNodes);
					
				closedNodes.push(currentNode);
			}
			
			openNodes.splice(0, 1);
		}
	}
}